/*******************************************
Module: zt_tree_redblack.c
E-Mail: 24zhutian@gmail.com
Notices: Copyright (c) 2007-2011 ls
*******************************************/

#include "zt_config.h"
#include "zt_tree_redblack.h"

ZT_API void zt_tree_redblack_init(zt_tree_redblack *t,zt_tree_redblack_node *nil)
{
	ZT_TREE_RB_BLACK(nil);
	nil->key=0;
	nil->parent=nil->left=nil->right=nil;
	
	t->nil=nil;
	t->root=nil;
}

static zt_inline void zt_tree_redblack_left_rotate(zt_tree_redblack *t,zt_tree_redblack_node *x)
{
	zt_tree_redblack_node* y;
	zt_tree_redblack_node* nil=t->nil;

	y=x->right;
	x->right=y->left;

	if(y->left!=nil){
		y->left->parent=x; 
	}
  
	y->parent=x->parent;   

	if(x==x->parent->left){
		x->parent->left=y;
	} 
	else{
		x->parent->right=y;
	}
	y->left=x;
	x->parent=y;
}

static zt_inline void zt_tree_redblack_right_rotate(zt_tree_redblack *t,zt_tree_redblack_node *x)
{
	zt_tree_redblack_node *y;
	zt_tree_redblack_node *nil=t->nil;
	
	y=x->left;
	x->left=y->right;
	
	if(nil!=y->right){
		y->right->parent=x; 
	}
	y->parent=x->parent;
	if(x==x->parent->left){
		x->parent->left=y;
	}
	else{
		x->parent->right=y;
	}
	y->right=x;
	x->parent=y;

}

ZT_API zt_tree_redblack_node* zt_tree_redblack_insert(zt_tree_redblack *t,zt_tree_redblack_node *n)
{
	zt_tree_redblack_node *x;
	zt_tree_redblack_node *y;
	zt_tree_redblack_node *nil=t->nil;

	n->left=n->right=nil;
	y=t->root;
	x=t->root->left;
	while(x!= nil){
		if(ZT_TREE_RB_EQ(n->key,x->key)){
			return(x);
		}
		y=x;
		x=ZT_TREE_RB_LT(n->key,x->key)?x->left:x->right;		
	}
	n->parent=y;
	if((y == t->root)||ZT_TREE_RB_LT(n->key,y->key)){ /* y->key > n->key */
		y->left=n;
	} 
	else{
		y->right=n;
	}

	ZT_TREE_RB_RED(n);
	while(ZT_TREE_RB_ISRED(n->parent)) { /* use sentinel instead of checking for root */
		if (n->parent == n->parent->parent->left) {
			y=n->parent->parent->right;
			if(ZT_TREE_RB_ISRED(y)){
				ZT_TREE_RB_BLACK(n->parent);
				ZT_TREE_RB_BLACK(y);
				ZT_TREE_RB_RED(n->parent->parent);
				n=n->parent->parent;
			} 
			else{
				if (n==n->parent->right){
					n=n->parent;
					zt_tree_redblack_left_rotate(t,n);
				}
				ZT_TREE_RB_BLACK(n->parent);
				ZT_TREE_RB_RED(n->parent->parent);
				zt_tree_redblack_right_rotate(t,n->parent->parent);
			} 
		} 
		else{
			y=n->parent->parent->left;
			if (ZT_TREE_RB_ISRED(y)){
				ZT_TREE_RB_BLACK(n->parent);
				ZT_TREE_RB_BLACK(y);
				ZT_TREE_RB_RED(n->parent->parent);
				n=n->parent->parent;
			}
			else{
				if (n==n->parent->left){
					n=n->parent;
					zt_tree_redblack_right_rotate(t,n);
				}
				ZT_TREE_RB_BLACK(n->parent);
				ZT_TREE_RB_RED(n->parent->parent);
				zt_tree_redblack_left_rotate(t,n->parent->parent);
			} 
		}
	}
 	ZT_TREE_RB_BLACK(t->root->left);
	
	return(0);
}

static zt_inline void zt_tree_redblack_deletefixup(zt_tree_redblack *t,zt_tree_redblack_node *x)
{
	zt_tree_redblack_node* root=t->root->left;
	zt_tree_redblack_node* w;
	
	while( ZT_TREE_RB_ISBLACK(x) && (root != x)){
		if(x==x->parent->left){
			w=x->parent->right;
			if(ZT_TREE_RB_ISRED(w)){
				ZT_TREE_RB_BLACK(w);
				ZT_TREE_RB_RED(x->parent);
				zt_tree_redblack_left_rotate(t,x->parent);
				w=x->parent->right;
			}
			if(ZT_TREE_RB_ISBLACK(w->right)&&ZT_TREE_RB_ISBLACK(w->left)){ 
				ZT_TREE_RB_RED(w);
				x=x->parent;
			} 
			else{
				if (ZT_TREE_RB_ISBLACK(w->right)) {
					ZT_TREE_RB_BLACK(w->left);
					ZT_TREE_RB_RED(w);
					zt_tree_redblack_right_rotate(t,w);
					w=x->parent->right;
				}
				ZT_TREE_RB_CPYCOLOR(w,x->parent);
				ZT_TREE_RB_BLACK(x->parent);
				ZT_TREE_RB_BLACK(w->right);
				zt_tree_redblack_left_rotate(t,x->parent);
				x=root;
			}
		} 
		else {
			w=x->parent->left;
			if(ZT_TREE_RB_ISRED(w)) {
				ZT_TREE_RB_BLACK(w);
				ZT_TREE_RB_RED(x->parent);
				zt_tree_redblack_right_rotate(t,x->parent);
				w=x->parent->left;
			}
			if(ZT_TREE_RB_ISBLACK(w->right)&&ZT_TREE_RB_ISBLACK(w->left)){ 
	  			ZT_TREE_RB_RED(w);
	  			x=x->parent;
			} 
			else{
				if(ZT_TREE_RB_ISBLACK(w->left)){
					ZT_TREE_RB_BLACK(w->right);
					ZT_TREE_RB_RED(w);
					zt_tree_redblack_left_rotate(t,w);
					w=x->parent->left;
				}
				ZT_TREE_RB_CPYCOLOR(w,x->parent);
				ZT_TREE_RB_BLACK(x->parent);
				ZT_TREE_RB_BLACK(w->left);
				zt_tree_redblack_right_rotate(t,x->parent);
				x=root;
			}
		}
	}
	ZT_TREE_RB_BLACK(x);
}

static zt_inline zt_tree_redblack_node* zt_tree_redblack_successor(zt_tree_redblack *t,zt_tree_redblack_node *n)
{
	zt_tree_redblack_node* y;
	zt_tree_redblack_node* nil=t->nil;
	zt_tree_redblack_node* root=t->root;

	if (nil != (y = n->right)) {
		while(y->left != nil) {
			y=y->left;
		}
	} 
	else{
		y=n->parent;
		while(n == y->right) {
			n=y;
			y=y->parent;
		}
		if(y==root){
			return(nil);
		}
		
	}
	return(y);
}

ZT_API void zt_tree_redblack_delete(zt_tree_redblack *t,zt_tree_redblack_node *n)
{
	zt_tree_redblack_node *y;
	zt_tree_redblack_node *x;
	zt_tree_redblack_node *nil=t->nil;
	zt_tree_redblack_node *root=t->root;
	
	y= ((n->left==nil)||(n->right==nil))?n:zt_tree_redblack_successor(t,n);
	x= (y->left == nil) ? y->right : y->left;
	if (root == (x->parent = y->parent)) {
		root->left=x;
	} 
	else{
		if (y == y->parent->left) {
			y->parent->left=x;
		}
		else{
			y->parent->right=x;
		}
	}
	if (y != n) {
		if(ZT_TREE_RB_ISBLACK(y)){
			zt_tree_redblack_deletefixup(t,x);
		}	  
		
		y->left=n->left;
		y->right=n->right;
		y->parent=n->parent;
		ZT_TREE_RB_CPYCOLOR(y,n);
		n->left->parent=n->right->parent=y;
		if(n == n->parent->left){
			n->parent->left=y;
		} 
		else{
			n->parent->right=y;
		}
	} 
	else{		
		if(ZT_TREE_RB_ISBLACK(y)){
			zt_tree_redblack_deletefixup(t,x);		
		}
	}
}

static void zt_tree_redblack_order_internal(zt_tree_redblack *t,zt_tree_redblack_node *n,void (*ZT_TREE_REDBLACK_CALLBACK)(zt_tree_redblack_node *))
{
	if(n==t->nil){
		return;
	}
	zt_tree_redblack_order_internal(t,n->left,ZT_TREE_REDBLACK_CALLBACK);
	ZT_TREE_REDBLACK_CALLBACK(n);
	zt_tree_redblack_order_internal(t,n->right,ZT_TREE_REDBLACK_CALLBACK);
}

ZT_API void zt_tree_redblack_order(zt_tree_redblack *t,void (*ZT_TREE_REDBLACK_CALLBACK)(zt_tree_redblack_node *))
{
	zt_tree_redblack_order_internal(t,t->root->left,ZT_TREE_REDBLACK_CALLBACK);
}

ZT_API zt_tree_redblack_node* zt_tree_redblack_query(zt_tree_redblack *t,unsigned int k)
{
	zt_tree_redblack_node *x=t->root->left;
	zt_tree_redblack_node *nil=t->nil;

	if(x==nil){
		return(0);
	}
	while(!ZT_TREE_RB_EQ(k,x->key)){
		if(ZT_TREE_RB_LT(k,x->key)){
			x=x->left;
		}
		else{
			x=x->right;
		}
		if(x==nil){
			return(0);
		}
	}
  	return(x);
}

ZT_API zt_tree_redblack_node* zt_tree_redblack_min(zt_tree_redblack *t)
{
	zt_tree_redblack_node *n=t->root;

	while (n->left != t->nil) {
        n = n->left;
    }
	
    return(n);
}

ZT_API zt_tree_redblack_node* zt_tree_redblack_max(zt_tree_redblack *t)
{
	zt_tree_redblack_node *n=t->root->left;
	
	while (n->right != t->nil) {
        n = n->right;
    }
	
    return(n);
}

